// POJ 3624

#include <iostream>
#include <queue>
#include <functional>
using namespace std;

int dp[2][13000];
//int dp[3500][13000];
int n, c;

int w[3500];
int v[3500];

int solve()
{
	int i = n - 1;
	// n - 1
	for (int j = 0; j <= c; j++)
		if (j >= w[i])
			dp[i & 1][j] = v[i];
		else
			dp[i & 1][j] = 0;
	i--;
	for (; i >= 0; i--)
	{
		for (int j = 0; j <= c; j++)
			if (j >= w[i])
				dp[i & 1][j] = max(dp[(i + 1) & 1][j], dp[(i + 1) & 1][j - w[i]] + v[i]);
			else
				dp[i & 1][j] = dp[(i + 1) & 1][j];
	}
	return dp[0][c];
}

// the items in [i, n - 1] and the bag capacity is j
int solve(int i, int j)
{
	if (dp[i][j] == -1)
	{
		// the last one
		if (i == n - 1)
		{
			if (j >= w[i])
				dp[i][j] = v[i];
			else
				dp[i][j] = 0;
		}
		else
		{
			if (j >= w[i])
			{
				dp[i][j] = max(solve(i + 1, j), solve(i + 1, j - w[i]) + v[i]);
			}
			else
				dp[i][j] = solve(i + 1, j);
		}
	}
	return dp[i][j];
}

int main()
{
	scanf("%d%d", &n, &c);
	for (int i = 0; i < n; i++)
		scanf("%d%d", w + i, v + i);
	printf("%d", solve());
	system("pause");
	return 0;
}